1. Field
The present disclosure relates to a method for correcting errors. In particular, it relates to a computer-implemented method for correcting transmission errors in a physical system.
2. Related Art
Finding sparse solutions to underdetermined systems of linear equations—a problem of great importance in signal processing, and design of robust communication channels—is in general NP-hard [9,21]. For example, the sparsest solution is given by
            (              P        0            )        ⁢                  min                  d          ∈                      R            m                              ⁢                                                d                                            l            0                          ⁢        subject        ⁢                                                  ⁢                                                ⁢        to        ⁢                                  ⁢        Fd              =            y      ~        ⁡          (              =        Fe            )      and solving this problem essentially requires exhaustive searches over all subsets of columns of F, a procedure which clearly is combinatorial in nature and has exponential complexity.
This computational intractability has recently led researchers to develop alternatives to (P0), and a frequently discussed approach considers a similar program in the l1-norm which goes by the name of Basis Pursuit [6]:
            (              P        1            )        ⁢                  min                  d          ∈                      R            m                              ⁢                                                d                                            l            1                          ⁢        subject        ⁢                                                  ⁢                                                ⁢        to        ⁢                                  ⁢        Fd              =      y    ~  where we recall that
                  d                    l      1        =            ∑              i        =        1            m        ⁢                  ⁢                                    d          i                            .      Unlike the l0-norm which enumerates the nonzero coordinates, the l1-norm is convex. It is also well-known [7] that (P1) can be recast as a linear program (LP).
Motivated by the problem of finding sparse decompositions of special signals in the field of mathematical signal processing and following upon the groundbreaking work of Donoho and Huo [11], a series of beautiful articles [16,12,13,14,24] showed exact equivalence between the two programs (P0) and (P1). In a nutshell, it has been shown that for m/2 by m matrices F obtained by concatenation of two orthonormal bases, the solution to both (P0) and (P1) are unique and identical provided that in the most favorable case, the vector e has at most 0.914√{square root over (m/2)} nonzero entries. This is of little practical use here since we are interested in procedures that might recover a signal when a constant fraction of the output is unreliable.
Using very different ideas and together with Romberg [3], the applicants proved that the equivalence holds with overwhelming probability for various types of random matrices provided that the number of nonzero entries in the vector e be of the order of m/log m [4,5]. In the special case where F is an m/2 by m random matrix with independent standard normal entries, [9] proved that the number of nonzero entries may be as large as ρ·m, where ρ>0 is some very small and unspecified positive constant independent of m.